/*
day438 
2020.11.8 
*/

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
		return help(nums,k,0,nums.size()-1);
    }
    
    int help(vector<int> &nums,int k,int l,int r)
    {
    	int pos=partition(nums,l,r);
		if(pos-l+1==k)
		{
			return nums[pos];
		}
		if(pos-l+1>k)
		{
			return help(nums,k,l,pos-1);
		}
		
		return help(nums,k-(pos-l+1),pos+1,r);
		
	}
    
    int partition(vector<int> &nums,int l,int r)
    {
    	int tem=nums[l];
    	while(l<r)
    	{
    		while(l<r && nums[r]<=tem) --r;
    		nums[l]=nums[r];
    		
    		while(l<r && nums[l]>=tem) ++l;
    		nums[r]=nums[l];
		}
		
		nums[l]=tem;
		
		return l;
	}
};

int main()
{
	return 0;
 } 
